package com.leetcode.题库;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @author 覃国强
 * @date 2022-05-12 18:58
 */
public class 题库_0169_多数元素 {

  static
  class Solution {

    // 投票法

    public int majorityElement(int[] nums) {
      if (nums == null || nums.length == 0) {
        return 0;
      }
      int candidate = nums[0];
      int count = 1;
      for (int i = 1; i < nums.length; ++i) {
        if (count == 0 || nums[i] == candidate) {
          candidate = nums[i];
          ++count;
        } else {
          --count;
        }
      }
      return candidate;
    }

    // 快排定基法

    public int majorityElement0(int[] nums) {
      int pivot = quickSort(nums, 0, nums.length - 1, nums.length / 2);
      return nums[pivot];
    }

    private int quickSort(int[] arr, int start, int end, int target) {
      if (start < end) {
        int pivot = partition(arr, start, end);
        if (pivot == target) {
          return pivot;
        }

        return pivot > target ?
            quickSort(arr, start, pivot - 1, target) :
            quickSort(arr, pivot + 1, end, target);
      }
      return end;
    }

    private int partition(int[] arr, int start, int end) {
      int pivot = ThreadLocalRandom.current().nextInt(start, end + 1);
      swap(arr, pivot, end);
      pivot = end;
      --end;
      while (start <= end) {
        while (start <= end && arr[start] <= arr[pivot]) {
          ++start;
        }
        swap(arr, start, pivot);
        pivot = start;
        ++start;
        if (start <= end) {
          while (start <= end && arr[end] >= arr[pivot]) {
            --end;
          }
          swap(arr, end, pivot);
          pivot = end;
          --end;
        }
      }
      return pivot;
    }

    private void swap(int[] arr, int i, int j) {
      if (i != j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }

  }

}
